package 高频题;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class 电话号码的字母组合_17 {

    //存放最终结果
    List<String> res = new ArrayList<>();

    //存放临时结果
    StringBuffer path = new StringBuffer();

    //使用HashMap存放字符与字符串对应关系
    Map<Character, String> phoneMap = new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};


    public List<String> letterCombinations(String digits) {
        if (digits.equals("") || digits.length() == 0) {
            return res;
        }
        //回溯
        backtraking(digits, 0);

        //返回结果
        return res;
    }

    /*
        参数：index：“23”中的索引
    */
    public void backtraking(String digits, int index) {

        //终止条件："23"遍历完成。
        if (index == digits.length()) {
            res.add(path.toString());
            return;
        }

        //获得index对应的数字
        char digit = digits.charAt(index);

        //获得数字对应的字符串
        String letter = phoneMap.get(digit);

        //遍历字符串中的字符
        for (int i = 0; i < letter.length(); i++) {
            //存入
            path.append(letter.charAt(i));

            //递归
            backtraking(digits, index + 1);

            //回溯
            path.deleteCharAt(index);
        }
    }
}